﻿//class Solution {
//public:
//	int memo[31]; // memory 备忘录，存储已经计算过的结果集
//	int dp[31];//动态规划数组
//
//
//	int fib(int n)
//	{
//		// 动态规划
//		dp[0] = 0; dp[1] = 1;
//		for (int i = 2; i <= n; i++)
//			dp[i] = dp[i - 1] + dp[i - 2];
//		return dp[n];
//	}
//
//};


//class Solution {
//public:
//	int memo[31]; // memory 备忘录，存储已经计算过的结果集
//	int dp[31];//动态规划数组
//
//
//	int fib(int n)
//	{
//		memset(memo, -1, sizeof(memo));
//		return dfs(n);
//	}
//
//	// 记忆化搜索
//	int dfs(int n)
//	{
//		if (memo[n] != -1)
//		{
//			return memo[n]; // 直接去备忘录拿值
//		}
//		if (n == 0 || n == 1)
//		{
//			memo[n] = n; // 记录到备忘录⾥⾯
//			return n;
//		}
//		memo[n] = dfs(n - 1) + dfs(n - 2); // 记录到备忘录⾥⾯
//		return memo[n];
//	}
//
//};